The present invention relates to an apparatus for finding the square root of a number, and especially to an apparatus for finding a square root in a digital system.
Inherently, square root operation is a sequential operation. The a square root digits are produced only after the sign of the remainders have been detected. As a result, square root operation is much slower than multiplication operation. Efforts have been made to up the square root operation. It is noted that the Analogous algorithm eliminates the restoring operations of the partial remainders. Another algorithm confines the square root digits either to be 1 or -1, depending on the signs of remainders. However, the bottleneck of those algorithms lies in sign detection of the remainder. Fast addition algorithms such as CLA (carry-lookahead addition) shorten the operation time, but result in complex hardware structures.
Recently, a square root algorithm based on SD (signed-digit) number representation was proposed which is much faster than the previous algorithms. This algorithm considerably shortens the time for remainder subtraction by using carry-propagation-free SD addition. However, it is much more complex because in each iteration the SD algorithm must check three most significant digit (MSD) bits of the remainder to decide the quotient digit in the set of {-1, 0, 1}, and then perform the SD addition. Moreover, the final SD result must be converted to binary representation. Also note that the signed-digit addition is more complicated than the conventional CSA, and it needs a complex square root decision circuit.
Another type of algorithm entirely avoids the slow subtract-detect-shift type of operation previously mentioned. It transforms the square root operation to a series of multiplication operations that converge to the original square root. Thus type of algorithm is often found in multiplier-based processors. It still uses a sequential type of operation to a certain degree, and obviously requires many more shift-and-add operations.
There is an on-line square root algorithm that facilitates serial/serial square root operation. This algorithm has advantages such as that: (a) it is pipelined at digit level; (b) all operands and results are input and output in a digit-serial fashion, and (c) result digits are on-line obtained after a few initial delays. On the other hand, among some of its disadvantages are: (a) it requires more complex three-input signed-digit addition operation; (b) it needs more complicated square root decision circuitry for range detection of the remainder; and (c) output results have to be converted to binary representations.